package fun.coding.leetcode;

public class PartitionList {

	public static void main(String[] args) {

	}
	
	// Simply construct 2 lists, small and large, and connect them together. 
	public ListNode partition(ListNode head, int x) {
		if (head == null || head.next == null) return head;
		
		ListNode cur = head;
		
		ListNode smallDummy = new ListNode(-1);
		ListNode small = smallDummy;
		
		ListNode largeDummy = new ListNode(-1);
		ListNode large = largeDummy;
		
		while (cur != null) {
			if (cur.val >= x) {
				large.next = cur;
				large = large.next;
			} else {
				small.next = cur;
				small = small.next;
			}
			ListNode next = cur.next;
			cur.next = null;
			cur = next;
		}
		
		small.next = largeDummy.next;
		return smallDummy.next;
	}

}
